package com.example.demo.arithmetic.datastructure.tree;

import java.util.LinkedList;

// 非递归实现前中后序遍历
public class TreeTraversal2 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(
                new TreeNode(new TreeNode(4), 2, null),
                1,
                new TreeNode(new TreeNode(5), 3, new TreeNode(6)));
        System.out.println("前序");
        preOrder(root);
        System.out.println("\n中序");
        inOrder(root);
        System.out.println("\n后序");
        postOrder(root);

//        LinkedList<TreeNode> stack = new LinkedList<>();
//        TreeNode curr = root;
//
//        while (curr != null || !stack.isEmpty()) {
//            if (curr != null) {
//                // 前序
//                System.out.println("去" + curr.val);
//                stack.push(curr);
//                curr = curr.left;
//            } else {
//                // 中序
//                TreeNode pop = stack.pop();
//                System.out.println("回" + pop.val);
//                curr = pop.right;
//            }
//        }

    }


    /**
     * 前序遍历 root->左->右
     *
     * @param node
     */
    static void preOrder(TreeNode node) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode curr = node;

        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                // 前序
                System.out.print(curr.val + "\t");
                stack.push(curr);
                curr = curr.left;
            } else {
                // 中序
                TreeNode pop = stack.pop();
                //System.out.println("回" + pop.val);
                curr = pop.right;
            }
        }
    }


    /**
     * 中序遍历 左->root->右
     *
     * @param node
     */
    static void inOrder(TreeNode node) {

        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode curr = node;

        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                // 前序
                //                System.out.println("去" + curr.val);
                stack.push(curr);
                curr = curr.left;
            } else {
                // 中序
                TreeNode pop = stack.pop();
                System.out.print(pop.val + "\t");
                curr = pop.right;
            }
        }
    }

    /**
     * 中序遍历 左->root->右
     *
     * @param node
     */
    static void postOrder(TreeNode node) {

        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode curr = node;
        TreeNode pop = null;
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                // 前序
                //                System.out.println("去" + curr.val);
                stack.push(curr);
                curr = curr.left;
            } else {
                // 后序
                TreeNode peek = stack.peek();
                if (peek.right == null || peek.right == pop) {
                    pop = stack.pop();
                    System.out.print(pop.val + "\t");
                } else {
                    curr = peek.right;
                }
            }
        }
    }
}


